package com.chj.leetcode.tijie850to900;

public class Code878_NthMagicalumber {
//	https://leetcode.jp/leetcode-878-nth-magical-number%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E4%BA%AB/
	public static int nthMagicalNumber(int N, int A, int B) {
		long pow = 1000000007;
		long maxNum = Math.min(A, B) * (long) N; // 结果的范围上限
		long minNum = Math.min(A, B); // 结果的范围下限
		long currentNumMid = (minNum + maxNum) / 2; // 范围中间数
		// 计算出A和B的最小公倍数
		int leastCommonMultiple = findLeastCommonMultiple(A, B);
		while (true) {
			// 计算出小于等于currentNum范围内存在多少A和B不重复的倍数count
			long count = currentNumMid / A + currentNumMid / B - currentNumMid / leastCommonMultiple;
			// 如果count为N，那么当前数为最接近结果的一个数字
			if (count == N) {
				// 如果currentNum在A和B之间，结果应是currentNum / 小数 * 小数
				// 如果currentNum大于A和B，结果应是currentNum / 大数 * 大数
				// 第一种情况，currentNum / 大数等于0，所以可以简化为下面的写法
				return (int) ((Math.max(currentNumMid / A * A, currentNumMid / B * B)) % pow);
			}
			// 如果count大于N，则需要在currentNum之前继续半分查找
			if (count > N) {
				maxNum = currentNumMid;
				currentNumMid = (currentNumMid + minNum) / 2;
			}
			// 如果count小于N，则需要在currentNum之后继续半分查找
			else {
				minNum = currentNumMid;
				// 这里注意一下避免死循环，如果新取得的currentNum与之前的值相同，
				// 需要将currentNum 加一
				// eg. currentNum = 2, maxNum = 3, (2 + 3) / 2 = 2;
				currentNumMid = (currentNumMid + maxNum) % 2 == 1 ? (currentNumMid + maxNum) / 2 + 1
						: (currentNumMid + maxNum) / 2;
			}
		}
	}

	// 计算两数的最小公倍数
	private static int findLeastCommonMultiple(int A, int B) {
		int index = 1; // 倍
		int min = Math.min(A, B); // 小数
		int max = Math.max(A, B); // 大数
		while (true) {
			// 如果小数的index倍大于等于大数，并且小数的index倍也是大数的倍数
			if (min * index >= max && min * index % max == 0) {
				// 当前小数的index倍便是2数的最小公倍数，返回。
				return min * index;
			}
			index++; // 加一倍继续循环
		}
	}

	public static int nthMagicalNumber02(int N, int A, int B) {
		long MOD = 1000_000_007;
		long L = lcm(A, B);
		long right = N * L;
		long left = 0;
		long mid = 0;
		while (left < right) {
			mid = (left + right) >>> 1; // 无符号右移
			long num = mid / A + mid / B - mid / L; // mid/L是mid/A和mid/B的交集，重复的部分，需要删除
//			if (num < N) {
//				left = mid + 1;
//			} else {
//				right = mid;
//			}
			if (num == N) {
//				return (int) (mid % MOD);
				right = mid;
			} else if (num < N) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return (int) (left % MOD);
	}

	// 最小公倍数 * 最大公约数 = A * B
	// 最小公倍数 = A * B / 最大公约数
	private static long lcm(int A, int B) {
		return ((long) A) / gcd(A, B) * B;
	}

	private static int gcd(int dividor, int remainder) {
		if (remainder == 0)
			return dividor;
		return gcd(remainder, dividor % remainder);
	}

//作者：nortondark
//链接：https://leetcode-cn.com/problems/nth-magical-number/solution/er-fen-fa-by-nortondark/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static int nthMagicalNumber03(int N, int A, int B) {
		long lcm = A * B / gcd03(A, B);
		long left = 2;
		long right = (long) 1e14;
		long M = (long) (1e9 + 7);

		while (left < right) {
			long mid = left + (right - left) / 2;
			long ans = mid / A + mid / B - mid / lcm;
			if (ans == N) {
				right = mid;
			} else if (ans < N) {
				left = mid + 1;
			} else if (ans > N) {
				right = mid - 1;
			}
		}
		return (int) (right % M);
	}

	public static int gcd03(int a, int b) {
		return (b == 0) ? a : gcd03(b, a % b);
	}

	public static void main(String[] args) {
//		最小公倍数
		System.out.println(lcm(4, 6));
//		最大公约数
		System.out.println(gcd(4, 6));
		System.out.println(findLeastCommonMultiple(4, 6));
		System.out.println(nthMagicalNumber(3, 4, 6));
		System.out.println(nthMagicalNumber02(3, 4, 6));
	}
}
